package leecode

import "sort"

func medianSlidingWindow(nums []int, k int) (result []float64) {
	windowsNum := make([]int, k)
	copy(windowsNum, nums[0:k])
	sort.Ints(windowsNum)
	result = append(result, middle(windowsNum, k)) //初始化窗口中的中位数
	for i := 1; i < len(nums)-k+1; i++ {
		windowsNum = delIndex(windowsNum, nums[i-1])  //删除窗口最左边的值
		windowsNum = addLast(windowsNum, nums[i+k-1]) //窗口右移
		result = append(result, middle(windowsNum, k))
	}
	return
}

// 求中位数
func middle(nums []int, k int) float64 {
	if k%2 == 0 {
		res := (float64(nums[k/2]) + float64(nums[k/2-1])) / 2.0 //偶数情况下的中位数
		return res
	}
	res := float64(nums[k/2])
	return res
}

// 删除窗口中排序前最左侧的元素
func delIndex(nums []int, target int) []int {
	for i := 0; i < len(nums); i++ {
		if nums[i] == target {
			return append(nums[:i], nums[i+1:]...)
		}
	}
	return nums
}

// 窗口右移
func addLast(nums []int, last int) []int {
	for i := 0; i < len(nums); i++ {
		if nums[i] > last {
			p := append([]int{last}, nums[i:]...)
			if i == 0 {
				return p
			}
			return append(nums[:i], p...)
		}
	}
	return append(nums, last)
}
